## 二维dp数组法
class Solution(object):
    def bagpack(self, weight, value, n):
        """
        weight: 物品重量list
        value: 物品价值list
        n: 背包最大容量
        """
        dp = [[0]*(n+1) for _ in range(len(weight))]
        for i in range(n+1):
            if i >= weight[0]:
                dp[0][i] = value[0]
        for i in range(1, len(weight)):
            for j in range(1, n+1):
                if weight[i] > j:
                    dp[i][j] = dp[i-1][j]
                else:
                    dp[i][j] = max(dp[i-1][j], value[i]+dp[i-1][j-weight[i]])
        return dp[-1][-1]
    

## 一维dp数组法
class Solution(object):
    def bagpack(self, weight, value, n):
        """
        weight: 物品重量list
        value: 物品价值list
        n: 背包最大容量
        """
        dp = [0]*(n+1)
        for i in range(len(weight)):
            for j in range(n, weight[i]-1, -1):
                dp[j] = max(dp[j], value[i]+dp[j-weight[i]])
        return dp[-1]


